#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 
# Copyright (c) 2017 Baidu.com, Inc. All Rights Reserved
# 

"""
File: run31.py
Author: zhangyang(zhangyang40@baidu.com)
Date: 2018/1/8 0008 14:55
"""
"""
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？
为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,
但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,
可以很快的求出任意非负整数区间中1出现的次数。
http://www.cnblogs.com/nailperry/p/4752987.html
"""
import math


class Solution:
    def NumberOf1Between1AndN_Solution(self, n, x):
        if n < 0 or x < 1 or x > 9:
            return 0
        i = 1
        high = n
        total = 0
        while high != 0:
            high = n / int(math.pow(10, i))  # 获取第i位的高位
            tmp = n % int(math.pow(10, i))
            curr = tmp / int(math.pow(10, i - 1))  # 获取第i位
            low = tmp % int(math.pow(10, i - 1))  # 获取第i位的低位
            if curr == x:
                total += high * int(math.pow(10, i - 1) + low + 1)
            elif curr < x:
                total += high * int(math.pow(10, i - 1))
            else:
                total += (high + 1) * int(math.pow(10, i - 1))
            i += 1
        return total
